perm filename GEM[00,BGB]1 blob
sn#097085 filedate 1974-04-16 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00009 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 3.0 Geometric Modeling Theory.
C00008 00003 3.1 Kinds of Geometric Models.
C00014 00004
C00019 00005
C00025 00006
C00027 00007 3.2 Polyhedron Modeling.
C00046 00008 3.3 Camera, Light and Image Modeling.
C00069 00009
C00071 ENDMK
C⊗;
3.0 Geometric Modeling Theory.
3.1 Kinds of Geometric Models.
3.2 Polyhedron Modeling.
3.3 Camera, Light and Image Modeling.
3.0 Introduction.
In the specific context of computer vision and graphics,
geometric modeling refers to constructing computer representations of
physical objects, cameras, images and light for the sake of
simulating their behavior. In the context of Artificial Intelligence,
a geometric model is a kind of world model; ignoring subtleties,
geometric world modeling is distinguished from semantic and logical
world modeling in that it is quantitative and numerical rather than
qualitative and symbolic. The notion of a world model requires an
external world environment to be modeled, an internal computer
environment to hold the model, and a task performing entity to use
the model. In the context of formal geometry, geometric modeling is a
synthetic problem, like a construction with ruler and straight edge
that requires a list of steps rather than a proof as in analytic
geometry or axiomatic geometry. The adjective "geometric" however is
quite apropos in that it literally means "world measure" which is
exactly the activity to be automated.
3.1 Kinds of Geometric Models.
The main problem of geometric modeling is to invent good
methods for representing arbitrary physical objects in a computer. A
physical object (for the moment) is something solid, rigid, opaque,
Newtonian, and macroscopic with a mathematically well behaved
surface. Physical objects include: the earth, telephones (excluding
the wire), roads (considered to be composed of pieces), and plastic
toy horses. In addition, physical objects can be moved about in
space, but two objects can not simultaneously occupy the same space
at the same time. The scope of the problem can be appreciated by
examining the virtues and drawbacks of the kinds of models listed in
the box.
---------------------------------------------------------
| TEN KINDS OF GEOMETRIC MODELS: |
| |
| Space Oriented: |
| |
| 1. 3-D Space Array. |
| 2. Recursive Cells. |
| 3. 3-D Density Function. |
| 4. 2-D Surface Functions. |
| 5. Parametric Surface Functions. |
| |
| Object Oriented: |
| |
| 6. Manifolds. |
| 7. Polyhedra. |
| 8. Volume Elements. |
| 9. Cross Sections. |
| 10. Skeletons. |
---------------------------------------------------------
For a naive start, first consider a 3-D array in which each
element indicates the presence or absence of solid matter in a cube
of space. Such a 3-D space array has the very desirible properties
of "spatial addressing" and "spatial uniqueness" in their most direct
and natural form. Spatial addressing refers to finding out what the
model contains within a distance R of a locus X,Y,Z; spatial
uniqueness refers to modeling the property that physical solids can
not occupy the same space. The main drawback of the 3-D space array
model is illustrated by the apparently legal FORTRAN statement:
DIMENSION SPACE(10000,10000,10000)
The problem with such a dimension statement is that no present day
computer memory is large enough to contain a 10↑15 element array.
Smaller space arrays arrays can be useful but necessarily can not
model large volumes with high resolution. A further drawback of space
arrays is that objects and surfaces are not readily accessible as
entities; that is a space array lack the desirible property of
"object coherence".
The space array idea can be salvaged (and must be salvaged)
by noticing that large portions of the array contain similar values.
By grouping blocks of elements with the same values together, the
addressing process becomes more complicated but the overall memory
required is reduced and the two desired properties can be maintained.
One way of doing this (which has been discovered in several
applications) is "recursive cells"; the whole space is considered to
be a cell; if the space is not homogeneous than the first cell is
divided into two (or four or eight) sub cells and the criterion is
applied again. This technique of recursive celling allows the spatial
sorting of objects, if the object models can be subdivided at each
recursion without losing the properties of the objects.
In the abstract, arbitrary physical objects are frequently
referred to as three dimensional density functions W=RHO(X,Y,Z).
Unfortunately such density functions can not be written out for
objects such as a typing chair or a plastic horse without resorting
to a programming language or an extensive table (which would be
equivalent to interpolating in a space array model). However, in the
special application of geodetic mapping, the shape of the land is
modeled by a two dimensional surface funtion Z = F(X,Y) which can be
expressed in a computer, albeit requires large tables.
By definition, a function is single valued; consequently the
description of even modestly complicated objects can not be expressed
directly as a single function of orthogonal rectilinear space
coordinates X, Y and Z. It is necessary either to adopt parametric
functions or to subdivide the object into portions that can be
described by simple functions of Cartesian variables. The latter
course of subdividing objects into portions is called segmentation is
discussed below under manifold modeling; the former course can be
illustrated be the example in figure (**) showing (X,Y,Z) locus of
the surface of a unit cube expressed as functions of (U,V) surface
coordinates. The advantage of parametric functions is that extended
arbitrary curve surfaces can be expressed; some of the disadvantages
are that parametric curves may be self intersecting, they can not be
locally modified, and the functions become impractically complex
before interesting objects are achieved.
At this point, we pass from space oriented models to object
oriented models. I wish to point out the mysterious dicotomy between
objects and the space that contains the objects, and observe that it
is indeed curious that intellectual entities group portions of their
perception into "objects" and that the objects change and interact in
spacetime. However, our goal is merely to simulate the properties of
objects in spacetime; rather than to explain them. In this thesis the
representation of time will receive no special attention. Although an
advanced problem solving robot will want to run world simulations
along multiple time paths, the problem of running one geometric world
simulation must be solved first.
Having postulated the existence of objects, I will proceed to
postulate another property of the objects to be modeled:
geometrically, a physical three dimensional object can be enclosed by
an unbroken two dimensional surface with an unabiguous inside and
outside. Which brings us to the mathematical topic (celebrated in
song by Tom Lehrer) of the algebraic topology of locally Euclidean
transitions of infinitely differentiable oriented Riemann manifolds.
A manifold is the mathematical abstraction of a surface; a Riemann
manifold has a metric function; an oriented manifold has a
unambiguous inside and an outside; and the phrase "infinitely
differentiable" can be taken to mean that the surface is smooth and
continuous.
Next, in order to talk about the topology of Riemann
manifolds it is necessary to introduce the 0-Simplex (vertex),
1-Simplex (edge), and 2-Simplex (triangle). In Analysis, it is
demonstrated that the surface of a Riemann manifold can be divided
into simplexs such that Eulers equations F-E+V=2-2*H is satisfied
(where F is the number of 2-simplexs, E is the number of 1-simplexs,
V is the number of 0-simplexs and H is the genus (number of handles)
of the manfold); and such that the surface of the manifold can be
approximated by local functions over each 2-simplex which are
Euclidean and which splice together correctly at all the 1-simplexs
(edges). Riemann manifolds provide a modern mathematical foundation
(i.e. calculus) for the kind of model which is the main topic of this
thesis, polyhedral models.
Polyhedra will be carefully defined in the next section. The
main inherent advantage of a polyhedra is its coherent surface
topology of faces, edges and vertices. Such a surface can be
subdivided without losing its coherence or the coherence of the
object. The disadvantages of polyhedra include the lack of spatial
uniqueness and spatial addressing; computation has to be done to
detect and prevent spatial conflict or to find the portions of an
entity occupying a given volume. Another disadvantage is that
polyhedra per se are not curved surfaces, however by associating an
appropriate function with each face a model of a 2-D Riemann manifold
(embedded in 3-D Euclidean space) can be made, which is a curved
object representation.
Arbitrary objects can also be described by listing a set of
cross sections taken at a sufficient number of cutting planes; this
is how the shape of a ship's hull or an airplane's wing is specified.
Cross sections have the interesting feature of good space modeling on
one axis. Forsaking arbitrary shaped objects, large classes of
things can be described in terms of a small set of basic volume
elements. For example, Roberts and others have built models of
familar objects using only rectangular and triangular right prisms.
Although, arbitrary solid polyhedra can be constructed out of
tetrahedrons (the 3-simplex); no significant modeling system exists
using this potentially interesting approach.
Skeletal models are based on abstracting an object into a
stick figure and by associating a diameter or set of cross sections
with the sticks. In particular, spine cross section models have been
pursued at Stanford by (Agin, Binford and Nervatia; Blum). Spine
cross section models have the advantage of being able to express many
object is a concise form suitable for recognition, however spine
cross section models can not be used direclty for arbitrary shapes.
Finally, it is useful to represent physical objects by a very weak
model such as by using sets of spheres or sets of surface points. It
is interesting to note that the "reality" that the robot in
Winograd's thesis could talk about, was a blocks world based on a
geometric model consisting of points, size of block, and a two paged
LISP routine name FINDSPACE.
To the best of my knowledge, this survey is complete; there
are no other significantly different kinds of geometric models. The
desirable properties that have turned up in this survey are list in
the box below.
---------------------------------------------------------------------
DESIRABLE PROPERTIES OF A GEOMETRIC MODEL.
1. Spatial Addressing.
2. Spatial Uniqueness.
3. Object Coherence with Divisibility.
4. Surface Coherence with Divisibility.
5. Shape generality.
6. Large Extent with High Resolution.
7. Readily Modifiable.
8. Suitable for photometric, kinematic and dynamic simulation.
9. Low (or even feasible) memory and computation requirements.
10. Potential for automatic model acquistion.
---------------------------------------------------------------------
3.2 Polyhedron Modeling.
Geometrically, a polyhedron is a simply connected finite
region of space composed of the union of a finite number of convex
polyhedra. A convex polyhedron is a non empty, simply connected,
finite region of space enclosed by a finite number of planes. The
boundary of the polyhedron is called its surface. The simply
connected regions of the surface belonging to only one plane are
called faces. The simply connected regions of the surface belonging
to exactly two planes are called edges; and the loci of the surface
where three or more planes interect are called vertices.
From the definition and the properties of planes, the local
topology of faces, edges and vertices can be derived. Edges are
bounded by two vertices and two faces. Faces are bounded by edges and
vertices. Vertices are bounded by faces and edges.
Topologically, the surface elements of a polyhedron form a
graph that satisfies Euler's F-E+V=2-2*H equation; where F, E and V
are the number of faces, edges and vertices of the polyhedron; and
where H is the number of holes in (or genus of) the polyhedron.
However, not all Eulerian graphs of faces, edges and vertices
correspond to solid polyhedra.
_____________________________________________________________________
Properties of a Solid Polyhedron:
1. Satisfies Eulers Equation F-E+V=2*B-2*H
2. All vertices and faces have three or more edges.
3. No edge intersects a face or vertex to which it doesn't belong.
4. All the vertices of a face are coplanar.
5. The volume measure is finite and positive.
__________________________________________________________
3.3 Camera, Light and Image Modeling.
Common to both computer graphics and visioN (irrespective
of the particular kind geometric model) is the necessity to model
the entities called camera, light and image so that pictures may
be synthesized or analysized.
An adequate version of the camera model that has become nearly
standard in computer graphics and vision can be specified by
by ten real numbers involving nine degrees of freedom.
First there is the camera lens center locus:
CX, CY, CZ, in world coordinates.
Afixed to the lens center is the camera frame of reference with unit
vectors i, j and k. When the image formed by the camera is placed in
correspondence to a display screen, the
unit vector i maps into the rightward positive x of the display
screen, and the unit vector j maps into the upward positive y of the
display screen, and the unit vector k comes out of the display screen
to form a right handed coordinate system. Together the three unit
vectors of the camera are the three by three rotation matrix:
IX, IY, IZ
JX, JY, JZ in world coordinates.
KX, KY, KZ
Next, there are three scales which determine the correspondence
between world size and image size. Observe that the world is measured
in physical units of length like meters or feet while computer images
come in integral sizes like 1024 by 1024 or 480 rows by 512 columns,
thus the conversion scales must be in terms of logical image units
per physical world units. In an actual television camera a minute
image (say 9mm by 12mm) is formed on a vidicon tube and that image
has a particular number of rows and columns. It is the little image
on the vidicon that we pretend to model by the six parameters:
LDX, LDY, LDZ Logical raster size.
PDX, PDY, FOCAL Physical raster size.
Where the number named FOCAL, is the focal plane distance which in
this model (with distant objects) can safely be equated with the lens
focal length and can be given in millimeters (conventional lens run
12.5mm to 75mm for 1" TV). The integer LDZ is an artifact so that
the units come out correctly in the Z dimension. Thus the scales
factors are defined:
SCALEX ← -FOCAL*LDX/PDX;
SCALEY ← -FOCAL*LDY/PDY;
SCALEZ ← FOCAL*LDZ;
The light scattering properties of ordinary surfaces can be
modeled by thinking of the surface as composed of zillions of little
differential mirrors. The orientation of each mirror is described by
two angles, its tilt from the normal vector of the surface and its
pan about the normal vector with respect to a specified reference
vector in the tangent plane of the surface. For a perfect reflecting
surface all the differential mirrors have a zero pan and tilt; for
isotropic conventional surfaces the statistical distribution of pan
orientations is flat and the distribution of tilt orientations is a
blip function; and for a perfect isotropic Lambert surfaces both the
pan and tilt distributions are flat.